//
// Created by lovep on 2025/4/25.
//

#include <cstdio>
#include <cstdlib>
#include "bitree.h"

Status BiTree_Create(BiTree &T) {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') T = NULL;
    else {
        T = (BiTree) malloc(sizeof(BiTNode)); //建立根结点
        T->data = ch;
        BiTree_Create(T->lchild);
        BiTree_Create(T->rchild);
    }
    return OK;
}


BiTree BiTree_PICreate(char PreOrder[], char InOrder[], int PreIndex, int InIndex, int count) //建二叉树操作
//已知一棵二叉树的先根遍历和中根遍历序列，建立这棵二叉树
{
    BiTree T;
    if (count > 0) //先根和中根非空，count 表示二叉树中结点数
    {
        char r = PreOrder[PreIndex]; //取先根遍历序列中的第一个元素
        int i = 0;
        for (; i < count; i++) //寻找根结点在中根遍历序列中的位置
        {
            if (r == InOrder[i + InIndex])
                break;
        }
        T = (BiTree) malloc(sizeof(BiTNode)); //建立根结点
        T->data = r;
        T->lchild = BiTree_PICreate(PreOrder, InOrder, PreIndex + 1, InIndex, i); //建立左子树
        T->rchild = BiTree_PICreate(PreOrder, InOrder, PreIndex + i + 1, InIndex + i + 1, count - i - 1); //建立右子树
    } else
        T = NULL;
    return T;
}

BiTree BiTree_IPCreate(char InOrder[], char PostOrder[], int InIndex, int PostIndex, int count) {
    // 已知一棵二叉树的中根遍历和后根遍历序列，建立这棵二叉树
    BiTree T;
    if (count > 0) {
        // 中根和后根非空，count表示二叉树中结点数
        char r = PostOrder[PostIndex + count - 1]; // 取后根遍历序列中的最后一个元素作为根
        int i = 0;
        for (; i < count; i++) {
            // 寻找根结点在中根遍历序列中的位置
            if (r == InOrder[i + InIndex])
                break;
        }
        T = (BiTree) malloc(sizeof(BiTNode)); // 建立根结点
        T->data = r;
        // 建立左子树（中序序列的前i个元素，后序序列的前i个元素）
        T->lchild = BiTree_IPCreate(InOrder, PostOrder, InIndex, PostIndex, i);
        // 建立右子树（中序序列的i+1之后元素，后序序列的i之后元素，数量为count-i-1）
        T->rchild = BiTree_IPCreate(InOrder, PostOrder, InIndex + i + 1, PostIndex + i, count - i - 1);
    } else {
        T = NULL;
    }
    return T;
}

Status BiTree_Copy(BiTree T1, BiTree &T2) //复制操作
//已知一棵二叉树 T1，T2 是由 T1 复制而得
{
    if (T1) {
        T2 = (BiTree) malloc(sizeof(BiTNode)); //为根结点 T2 分配空间
        if (!T2) //空间分配失败
            return ERROR;
        T2->data = T1->data; //根结点 T2 的数据域值与根结点 T1 相等
        BiTree_Copy(T1->lchild, T2->lchild); //复制左子树
        BiTree_Copy(T1->rchild, T2->rchild); //复制右子树
    } else
        T2 = NULL;
    return OK;
}

int BiTree_PreCompare(BiTree T1, BiTree T2) //比较操作
//用先根遍历方法判断两棵二叉树是否相等
{
    if (!T1 && !T2) return 1;
    if (T1 && T2)
        if (T1->data == T2->data)
            if (BiTree_PreCompare(T1->lchild, T2->lchild) &&
                BiTree_PreCompare(T1->rchild, T2->rchild))
                return 1;
    return 0;
}

Status BiTree_PrePrint(BiTree T) {
    if (T) {
        printf("%c", T->data);
        BiTree_PrePrint(T->lchild);
        BiTree_PrePrint(T->rchild);
    }
    return OK;
}

Status BiTree_InPrint(BiTree T) {
    if (T) {
        BiTree_InPrint(T->lchild);
        printf("%c", T->data);
        BiTree_InPrint(T->rchild);
    }
    return OK;
}

Status BiTree_PostPrint(BiTree T) {
    if (T) {
        BiTree_PostPrint(T->lchild);
        BiTree_PostPrint(T->rchild);
        printf("%c", T->data);
    }
    return OK;
}

// int BiTree_IsSame(BiTree T1, BiTree T2) {
//     if (T1 == NULL && T2 == NULL) {
//         return 1;
//     }
//     if (T1 == NULL || T2 == NULL) {
//         return 0;
//     }
//     if (T1->data != T2->data) {
//         return 0;
//     }
//     return BiTree_IsSame(T1->lchild, T2->lchild)
//            && BiTree_IsSame(T1->rchild, T2->rchild);
// }

Status BiTree_CountNode(BiTree T, int &num) {
    if (T) {
        num += 1;
        BiTree_CountNode(T->lchild, num);
        BiTree_CountNode(T->rchild, num);
    }
    return OK;
}

Status BiTree_CountLeafNode(BiTree T, int &num) {
    if (T) {
        if (T->lchild == NULL && T->rchild == NULL) {
            num += 1;
        } else {
            BiTree_CountLeafNode(T->lchild, num);
            BiTree_CountLeafNode(T->rchild, num);
        }
    }
    return OK;
}

int BiTree_Depth(BiTree T) {
    int depth = 0;
    if (T) {
        int dl = BiTree_Depth(T->lchild);
        int dr = BiTree_Depth(T->rchild);
        depth = 1 + (dl > dr ? dl : dr);
    }
    return depth;
}

BiTree BiTree_SearchNode(BiTree T, TElemType data, char path[], int count, char symbol) {
    if (T) {
        if (count != -1) path[count] = symbol;

        if (T->data == data) {
            path[count + 1] = '\0';
            return T;
        }

        BiTree v1 = BiTree_SearchNode(T->lchild, data, path, count + 1, 'L');
        if (v1) return v1;
        BiTree v2 = BiTree_SearchNode(T->rchild, data, path, count + 1, 'R');
        if (v2) return v2;
    }
    return NULL;
}
